We looked and looked. We had trouble with the clues too though; came
up with three possible general locations (based on differing
interpretations of the clues) and searched them all quite thoroughly.

If box owners want to contact me privately with clue clarification I
may be able to get back to the marina before I leave Victoria, to
ascertain whether the box is actually missing or we just couldn't find
it. Though I expect it is the former, three adults and two
enthusiastic children spent well over an hour looking under every
possible rock. I'll be in Victoria another 5 days.

Sora for the Chicken-counters